package E_2024;

import java.util.Arrays;

/*
    从一个 N * M（N ≤ M）的矩阵中选出 N 个数，任意两个数字不能在同一行或同一列，求选出来的 N 个数中第 K 大的数字的最小值是多少。
输入描述：
    输入矩阵要求：1 ≤ K ≤ N ≤ M ≤ 150
输入格式：
    N M K
    N*M矩阵
输出描述：
    N*M 的矩阵中可以选出 M! / N! 种组合数组，每个组合数组种第 K 大的数中的最小值。无需考虑重复数字，直接取字典排序结果即可。
    备注：
    注意：结果是第 K 大的数字的最小值
示例1：
    输入：
    3 4 2
    1 5 6 6
    8 3 4 3
    6 8 6 3
    输出：
    3
    说明：
    N*M的矩阵中可以选出 M！/ N！种组合数组，每个组合数组种第 K 大的数中的最小值；
 */
public class E_200_29 {
    public static void main(String[] args) {
        System.out.println(ans(new int[][]{{1,5,6,6},{8,3,4,3},{6,8,6,3}},2));
    }
    static int ans = Integer.MAX_VALUE;
    public static int ans(int[][] arr, int num){
        int[] row = new int[arr.length];
        int[] lin = new int[arr[0].length];
        dfs(row,lin, arr, num, new int[Math.min(row.length,lin.length)], 0);
        return ans;
    }

    private static void dfs(int[] row, int[] lin, int[][] arr, int num, int[] temp, int index) {
        if (index >= temp.length){
            System.out.println(Arrays.toString(temp));
            int[] xx = Arrays.copyOf(temp,temp.length);
            Arrays.sort(xx);
            ans = Math.min(ans, xx[num-1]);
            return;
        }
        for (int i = 0; i < row.length; i++) {
            if (row[i] == 1) continue;
            row[i] = 1;
            for (int j = 0; j < lin.length; j++) {
                if (lin[j] == 1) continue;
                lin[j] = 1;
                temp[index] = arr[i][j];
                dfs(row,lin,arr,num,temp,index + 1);
                temp[index] = 0;
                lin[j] = 0;
            }
            row[i] = 0;
        }
    }

    public static int ans1(int[][] arr, int num){
        int max = 0;
        for (int[] ints : arr) {
            for (int anInt : ints) {
                max = Math.max(anInt, max);
            }
        }
        int[] temp = new int[max];
        for (int[] ints : arr) {
            for (int anInt : ints) {
                temp[anInt-1] = 1;
            }
        }
        for (int i = 0; i < temp.length; i++) {
            if (num == 0) return i;
            if (temp[i] != 0) num--;
        }
        return -1;
    }
}
